package com.wzq.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution46 {


    /***
     * 插入法
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        for(int i=0;i<len;i++){
            if(i == 0){
                List<Integer> l = new LinkedList<Integer>();
                l.add(nums[0]);
                rst.add(l);
            }else{
                int size = rst.size();
                for(int j=0;j<size;j++){
                    List<Integer> l = rst.get(j);
                    for(int k=1;k<=l.size();k++){
                        List<Integer> tl = new LinkedList<Integer>(l);
                        tl.add(k,nums[i]);
                        rst.add(tl);
                    }
                    l.add(0,nums[i]);
                }
            }
        }
        return rst;
    }


    private static void swap(int[] arr,int i,int j){
        if(i != j){
            arr[i] = arr[i]^arr[j];
            arr[j] = arr[i]^arr[j];
            arr[i] = arr[i]^arr[j];
        }
    }

/***********递归法 **/


    public static List<List<Integer>> permute2(int[] nums){

        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        permute2(nums,0,rst);
        return rst;
    }

    public static void permute2(int[] nums,int k,List<List<Integer>> rst){

        if (k == nums.length-1){
            rst.add(arrToList(nums));
        }else{
            for (int i=k;i<nums.length;i++){
                swap(nums,i,k);
                permute2(nums,k+1,rst);
                swap(nums,i,k);
            }
        }
    }

    private static List<Integer> arrToList(int[] nums){
        List<Integer> l = new ArrayList<Integer>(nums.length);
        for (int n:nums){
            l.add(n);
        }
        return l;
    }


    public static void main(String[] args) {
        List<List<Integer>> l = permute2(new int[]{1,1, 2, 3});
        System.out.println(l);

    }
    

}